package com.leetcode.array.smallestlength.demo3;

import java.util.*;

/**
 * @Author Zan
 * @Create 2024/5/9 7:52
 * @ClassName: Test
 * @Description : https://leetcode.cn/problems/minimum-window-substring/description/  最小覆盖子串
 */
public class Test {
    public static void main(String[] args) {
        // s = "ADOBECODEBANC", t = "ABC"
        String s = "BbBABaABbbb";
        String t = "aA";
//        Solution solution = new Solution();
//        String s1 = solution.minWindow(s, t);
//        System.out.println(s1);

        Solution2 solution2 = new Solution2();
        String s2 = solution2.minWindow(s, t);
        System.out.println(s2);

//        Solution2 solution2 = new Solution2();
//        String s2 = solution2.removeChars(s, t);
//        System.out.println(s2);
    }
}


// 粗暴的滑动窗口 - 未优化过
class Solution {

    Map<Character, Integer> requireMap = new LinkedHashMap<>();
    Map<Character, Integer> map = new LinkedHashMap<>();

    public String minWindow(String s, String t) {
        for (int i = 0; i < t.length(); i++) {
            requireMap.put(t.charAt(i), requireMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int start = 0;
        int subLen = Integer.MAX_VALUE;
        int end = 0;
        int startResult = 0;
        int endResult = 0;
        for (end = 0; end < s.length(); end++) {
            map.put(s.charAt(end), map.getOrDefault(s.charAt(end), 0) + 1);
            while (check()) {
                // 获取最短的长度
                if (subLen > end - start + 1) {
                    // 获取最小的位置
                    subLen = Math.min(subLen, end - start + 1);
                    startResult = Math.max(startResult, start);
                    endResult = Math.max(endResult, end + 1);
                }
                // 前面的已经筛选过了，因此需要筛选后面有没有更加好的了
                // 先删除再++
                map.put(s.charAt(start), map.get(s.charAt(start)) - 1);
                if (map.getOrDefault(s.charAt(start), 0) == 0) {
                    map.remove(s.charAt(start));
                }
                start++;
            }
        }
        return start - 1 == -1 ? "" : s.substring(startResult, endResult);
    }

    public boolean check() {
        // 便利循环requeireMap，判断map中是否有
        Set<Map.Entry<Character, Integer>> entrySet = requireMap.entrySet();
        for (Map.Entry<Character, Integer> entry : entrySet) {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            if (map.getOrDefault(key, 0) < value) {
                // 说明没有
                return false;
            }
        }
        return true;
    }
}

// 优化 - 处理传入的参数，前面和末尾的无用的参数去除
class Solution2 {

    Map<Character, Integer> requireMap = new LinkedHashMap<>();
    Map<Character, Integer> map = new LinkedHashMap<>();

    public String minWindow(String s, String t) {
        String newS = removeChars(s, t);
        for (int i = 0; i < t.length(); i++) {
            requireMap.put(t.charAt(i), requireMap.getOrDefault(t.charAt(i), 0) + 1);
        }
        int start = 0;
        int subLen = Integer.MAX_VALUE;
        int end = 0;
        int startResult = 0;
        int endResult = 1;
        for (end = 0; end < newS.length(); end++) {
            map.put(newS.charAt(end), map.getOrDefault(newS.charAt(end), 0) + 1);
            while (check() && startResult < endResult) {
                // 获取最短的长度
                if (subLen > end - start + 1) {
                    // 获取最小的位置
                    subLen = Math.min(subLen, end - start + 1);
                    startResult = Math.max(startResult, start);
                    endResult = Math.max(endResult, end + 1);
                }
                // 前面的已经筛选过了，因此需要筛选后面有没有更加好的了
                // 先删除再++
                map.put(newS.charAt(start), map.get(newS.charAt(start)) - 1);
                if (map.getOrDefault(newS.charAt(start), 0) == 0) {
                    map.remove(newS.charAt(start));
                }
                start++;
            }
        }
        return start - 1 == -1 ? "" : newS.substring(startResult, endResult);
    }

    public boolean check() {
        // 便利循环requeireMap，判断map中是否有
        Set<Map.Entry<Character, Integer>> entrySet = requireMap.entrySet();
        for (Map.Entry<Character, Integer> entry : entrySet) {
            Character key = entry.getKey();
            Integer value = entry.getValue();
            if (map.getOrDefault(key, 0) < value) {
                // 说明没有
                return false;
            }
        }
        return true;
    }

    public String removeChars(String s, String t) {
        StringBuilder sb = new StringBuilder(s);
        // 从头部开始删除
        for (int i = 0; i < sb.length(); i++) {
            if (t.contains(String.valueOf(sb.charAt(i)))) {
                break;
            } else {
                sb.deleteCharAt(i);
                i--; // 删除一个字符后，需要将索引回退一步
            }
        }

        for (int j = sb.length(); j > 0; j--) {
            if (t.contains(String.valueOf(sb.charAt(j - 1)))) {
                break;
            } else {
                sb.deleteCharAt(j - 1);
            }
        }
        return sb.toString();
    }
}

// 2ms的滑动窗口
class Solution3 {
    public String optimizeString(String s, String t) {
        // 记录 t 中字符的出现情况
        int[] tMap = new int[256];
        for (char c : t.toCharArray()) {
            tMap[c]++;
        }

        int left = 0, right = 0; // 双指针，分别表示子串的起始和结束位置
        int minLength = Integer.MAX_VALUE; // 最小子串长度
        int minLeft = 0; // 最小子串的起始位置
        int count = t.length(); // 记录子串中还需要匹配的 t 中字符的数量

        // 开始滑动窗口
        while (right < s.length()) {
            char rightChar = s.charAt(right);
            if (tMap[rightChar] > 0) {
                count--;
            }
            tMap[rightChar]--;
            right++;

            // 当 count 为 0 时，表示当前子串包含 t 中所有字符
            while (count == 0) {
                // 更新最小子串的长度和起始位置
                if (right - left < minLength) {
                    minLength = right - left;
                    minLeft = left;
                }

                // 移动左指针
                char leftChar = s.charAt(left);
                tMap[leftChar]++;
                if (tMap[leftChar] > 0) {
                    count++;
                }
                left++;
            }
        }
        return minLength == Integer.MAX_VALUE ? "" : s.substring(minLeft, minLeft + minLength);
    }
}